package ext;
import java.io.BufferedInputStream;
import java.util.*;
import org.junit.*;
public class Ex40 {

    class Solution {
        public List<List<Integer>> combinationSum2(int[] candidates, int target) {
            len = candidates.length;
            Arrays.sort(candidates);
            res = new ArrayList<>();
            dfs(candidates, 0, target, new ArrayDeque<>());
            return res;
        }


        int len;
        List<List<Integer>> res;
        public void dfs(int[] nums, int idx, int tar, Deque<Integer> deque) {
            if (tar == 0) {
                res.add(new ArrayList<>(deque));
                return;
            }
            if (tar < 0) {
                return;
            }

            for (int i = idx; i < len; i++) {
                /**
                 * nums = {1, 2, 2, 3}
                 * 递归树中出现：
                 *  1
                 * 2 2
                 * 的情况，需要把右分支剪去，因为他与左分支重复
                 * 而
                 *          1
                 *      2
                 *  2
                 * 不应该剪去第三层
                 */
                if (i > idx && nums[i - 1] == nums[i]) {
                    continue;
                }
                deque.offerLast(nums[i]);
                //这一步选取了当前位置，前面的不再选取
                dfs(nums, i + 1, tar - nums[i], deque); 
                deque.removeLast();
            }
        }


        public void dfs2(int[] nums, int tar, Deque<Integer> deque) {
            if (tar == 0) {
                res.add(new ArrayList<>(deque));
                return;
            }
            if (tar < 0) {
                return;
            }

            //从idx开始搜索，每个位置必定会深入递归
            //由于保证了每个位置都被选取，对于同级的重复元素会被剪枝
            for (int i = 0; i < len; i++) {
                if (flag[i] || i > 0 && nums[i - 1] == nums[i] && !flag[i - 1]) {
                    //上一个重复元素没被选，其实是在退出递归时消除分支的污染
                    //这个元素的情况已经试过，且当前i的可能比前面还要小
                    continue;
                }
                //必定选可以选的元素
                flag[i] = true;
                deque.addLast(nums[i]);
                dfs2(nums, tar - nums[i], deque);
                deque.removeLast();
                flag[i] = false;
            }
        }
    }

    @Test
    public void test1() {
        //[10,1,2,7,6,1,5]
// 8
// [2,5,2,1,2]
// 5
        Solution s = new Solution();
        int[] nums = new int[]{10,1,2,7,6,1,5};
        System.out.println(s.combinationSum2(nums, 8));
        
    }

    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        len = candidates.length;
        flag = new boolean[len];
        res = new ArrayList<>();
        set = new HashSet<>();
        dfs(candidates, 0, target, new ArrayList<>());
        return res;
    }   

    int len;
    boolean[] flag;
    Set<String> set;
    List<List<Integer>> res;
    public void dfs(int[] nums, int idx, int tar, List<Integer> cur) {
        if (idx == len) {
            if (tar == 0) {
                Queue<Integer> queue = new PriorityQueue<>(cur);
                StringBuilder sb = new StringBuilder();
                while (!queue.isEmpty()) {
                    sb.append(queue.poll() + "_");
                }
                if (!set.contains(sb.toString())) {
                    set.add(sb.toString());
                    res.add(new ArrayList<>(cur));
                }
            }
            return;
        }

        //既然走到这里，tar必定>0
        dfs(nums, idx + 1, tar, cur); //不取当前值
        if (tar >= nums[idx]) {
            cur.add(nums[idx]);
            dfs(nums, idx + 1, tar - nums[idx], cur); //取当前值
            cur.remove(cur.size() - 1);
        }
    }

    @Test
    public void test() {
        String s = "[1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1]";
        String[] ss = s.split("\\s*");
        System.out.println(ss.length);
        System.out.println(ss[0]);
    }

    public static void main(String[] args){
        Scanner sc = new Scanner(new BufferedInputStream(System.in));
        String s = sc.nextLine();

        s = s.substring(1, s.length() - 1);
        String[] ss = s.split("\\s*");
        int[] nums = Arrays.stream(ss).map(Integer::parseInt).mapToInt(Integer::valueOf).toArray();
        // sc.next();
        int tar = sc.nextInt();

        System.out.println(new Ex40().combinationSum2(nums, tar));
        sc.close();
    }

    //

}